package pers.qianyu.month_202012.date_20201225.dp_bag2;

/**
 * 1538. 卡牌游戏 II
 * https://www.lintcode.com/problem/card-game-ii/description
 * - 01背包求最值
 *
 * @author mizzle rain
 * @date 2020-12-25 21:43
 */
public class CardGame {
    /**
     * @param cost:        costs of all cards
     * @param damage:      damage of all cards
     * @param totalMoney:  total of money
     * @param totalDamage: the damage you need to inflict
     * @return: Determine if you can win the game
     */
    public boolean cardGame(int[] cost, int[] damage, int totalMoney, int totalDamage) {
        int[] dp = new int[totalMoney + 1];
        for (int i = 0; i < cost.length; i++) {
            int c = cost[i];
            int d = damage[i];
            for (int money = totalMoney; money >= c; money--) {
                dp[money] = Math.max(dp[money], dp[money - c] + d);
            }
        }
        return dp[totalMoney] >= totalDamage;
    }

    public static void main(String[] args) {
        int[] cost = {1, 2, 3, 4, 5};
        int[] damage = {1, 2, 3, 4, 5};
        boolean result = new CardGame().cardGame(cost, damage, 10, 10);
        System.out.println("result = " + result);
    }
}
